package com.gitee.feizns.explore.data_structure.union_find;

/**
 * @author feizns
 * @since 2020/3/11
 */
public class QuickFind implements UnionFind {

    private final int[] ids;

    public QuickFind(int size) {
        this.ids = new int[size];
        for (int i = 0; i < size; i++)
            this.ids[i] = i;
    }

    @Override
    public int size() {
        return ids.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        if ( i != j ) {
            for (int k = 0; k < ids.length; k++) {
                if ( ids[k] == i )
                    ids[k] = j;
            }
        }
    }

    private int find(int p) {
        return ids[p];
    }

}
